Compare-and-swap

Compare-and-swap (CAS) est une instruction atomique utilisée dans les systèmes multiprocesseurs ou multi-cœurs utilisant une mémoire partagée. Elle compare la valeur stockée à une adresse mémoire donnée à l'un de ses arguments et, en cas d'égalité, écrit une nouvelle valeur à cette adresse. Selon les implémentations, elle signale si l'écriture a réussi soit en renvoyant une valeur booléenne, soit en renvoyant la valeur lue en mémoire.

L'instruction CAS simple ne présente presque aucun problème au niveau de la synchronisation de l'adresse mémoire auquel elle pointe, sauf dans un cas précis décrit comme le problème ABA (en).

Architectures supportées

Cette opération de synchronisation est supportée par plusieurs architectures contemporaines, notamment sur Intel, AMD, et Oracle. Sur les architectures de Intel et AMD, cette instruction est appelée CMPXCHG, tandis que sur Oracle SPARC systems, elle est appelée CAS.

Leur fonctionnement reste globalement similaire. Contrairement à l'opération abstraite, l'instruction processeur prend 3 arguments : une adresse mémoire a, une valeur attendue e, et une valeur de mise à jour v, et retourne une valeur booléenne. Si la valeur contenue à l'adresse mémoire a contient la valeur attendue e, écrire la nouvelle valeur v à cette adresse et retourner vrai, sinon laisser la mémoire intacte et retourner faux.

Processeurs Intel

La première instruction de type CAS est apparue en premier en 1989 sur le processeur Intel 80486.

Sur les processeurs Intel, il existe deux instructions similaires qui implémentent l'instruction CAS : CMPXCHG (compare and exchange) et CMPXCHG8B (compare and exchange 8 bytes). L'instruction CMPXCHG requiert 3 opérandes : une opérande de source dans un registre, une autre opérande de source dans le registre EAX et enfin une opérande de destination. Si les valeurs contenues dans l'opérande de destination et dans le registre EAX sont égales, alors l'opérande de destination est remplacée par la valeur de la deuxième opérande de source (la valeur qui ne se trouve pas dans le registre EAX). Sinon, la valeur contenue dans l'opérande de destination est chargée dans le registre EAX.

Cette instruction est utilisée pour tester et modifier des sémaphores. Si elle teste qu'un sémaphore est libre, alors elle le marquera comme étant alloué. Sinon elle renverra l'ID de son propriétaire. Elle peut être utilisée tout aussi bien en architecture monocœur qu'en multicœurs. Dans ce dernier cas, un préfixe LOCK peut être ajouté devant l'instruction pour la forcer à être atomique.

Exemple d'utilisation

Voici un exemple d'utilisation tiré du noyau de Linux, la fonction rtc_cmos_read() , désassemblée, utilise l'instruction suivante :

 lock cmpxchg    %edx, cmos_lock

On peut la lire de la façon suivante :

• prefix : lock
• opcode: cmpxchg
• source-operand: %edx
• destination-operand: cmos_lock

Variantes

CMPXCHG8B fonctionne de manière similaire mais avec des valeurs 64-bit au lieu de valeurs 32-bit, elle peut également être accompagné ou non du préfixe LOCK pour la forcer à agir de manière atomique. Elle prend également 3 opérandes : une valeur 64-bit dans EDX:EAX, une valeur 64-bit dans ECX:EBX, et une opérande de destination en mémoire (dont la valeur n'est pas précisée). L'instruction compare la valeur contenue dans EDX:EAX avec la valeur de l'opérande de destination. Si elles sont égales, la valeur des registres ECX:EBX est enregistrée dans l'opérande de destination, sinon la destination est chargée dans les registres EDX:EAX.

Il existe également une instruction uniquement disponible pour les architectures 64-bit, appelée CMPXCHG16B, qui est une extension de l'instruction CMPXCHG8B et opère sur des données de 128-bit.

Problème du Consensus

L'instruction Compare-and-Swap fait l'objet d'un théorème particulier en ce qui concerne le problème du consensus.

Théorème — Un registre qui fournit à la fois les méthodes compareAndSwap() et Get() possède un numéro de consensus infini.

Problème ABA

Le problème ABA (en) résulte d'un défaut lié au fonctionnement même de l'instruction CAS. Elle apparait communément dans la situation suivante :

1. Une application lit une valeur a d'une adresse mémoire donnée, et calcule une nouvelle valeur c pour cette adresse.
2. Elle essaye de sauvegarder c, mais seulement si la valeur a à l'adresse mémoire n'a pas été changée depuis qu'elle a été lue.
3. Pendant ce temps-là, un autre thread a réécrit l'adresse mémoire de a avec une valeur b, puis plus tard réécrit a à cet emplacement-là.

L'opération CAS va remplacer a avec c, mais peut-être que l'application n'aura pas agit comme on s'y attendait. Par exemple, si l'adresse a mémorise un pointeur, la nouvelle valeur a sera peut-être l'adresse d'un objet recyclé.